﻿#include <stdio.h>
#include <iostream>
#include <time.h>
#include <windows.h>
#include <stack>
#include <deque>
#define L 0
#define R 1
#define U 2
#define D 3
using namespace std;

void print(COORD p, char c)//在p所在的位置输出CHAR c所指的字符
{
	HANDLE Houtput = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleCursorPosition(Houtput, p);
	printf("%c", c);
}
bool operator==(COORD& A, COORD& B)
{
	if (A.X == B.X && A.Y == B.Y)return true;
	return false;
}
bool operator!=(COORD& A, COORD& B) { return !(A == B); }

class snake {
private:
	COORD food;//食物位置
	deque<COORD>body;
	bool board[16][16];
	bool path_board[16][16];
	short path[16][16] = {
	{R,R,R,R,R,R,R,R,R,R,R,R,R,R,R,D},
	{U,L,L,L,L,L,L,L,L,L,L,L,L,L,L,D},
	{R,R,R,R,R,R,R,R,R,R,R,R,R,D,U,D},
	{U,D,L,L,L,L,L,L,L,L,L,L,L,D,U,D},
	{U,D,R,R,R,R,R,R,R,R,R,D,U,D,U,D},
	{U,D,U,D,L,L,L,L,L,L,L,D,U,D,U,D},
	{U,D,U,D,R,R,R,R,R,D,U,D,U,D,U,D},
	{U,D,U,D,U,D,L,L,L,D,U,D,U,D,U,D},
	{U,D,U,D,U,D,R,R,U,D,U,D,U,D,U,D},
	{U,D,U,D,U,D,U,L,L,L,U,D,U,D,U,D},
	{U,D,U,D,U,R,R,R,R,R,U,D,U,D,U,D},
	{U,D,U,D,U,L,L,L,L,L,L,L,U,D,U,D},
	{U,D,U,R,R,R,R,R,R,R,R,R,U,D,U,D},
	{U,D,U,L,L,L,L,L,L,L,L,L,L,L,U,D},
	{U,R,R,R,R,R,R,R,R,R,R,R,R,R,U,D},
	{U,L,L,L,L,L,L,L,L,L,L,L,L,L,L,L},
	};
public:
	snake() {
		init_board(board);
		body.push_back({ 1,0 });
		body.push_back({ 0,0 });
		print(body[0], '*');
		print(body[1], '*');
		board[0][0] = true;
		board[1][0] = true;
		init_board(path_board);
		init_path();
		set_path_board({ 0,0 }, true);
		create_food();

	}
	void init_board(bool tmp[16][16]) {
		for (int i = 0; i < 16; i++) {
			for (int j = 0; j < 16; j++)tmp[i][j] = false;//点阵全初始为false
		}
	}
	bool is_not_all_true(bool tmp[16][16]) {
		for (int i = 0; i < 16; i++) {
			for (int j = 0; j < 16; j++) { if (tmp[i][j] == false)return true; }
		}return false;
	}/*
	void _print() {
		for (int y = 0; y < 16; y++) {
			for (int x = 0; x < 16; x++)
				switch (path[x][y]) {
				case L:printf("L "); break;
				case R:printf("R "); break;
				case D:printf("D "); break;
				case U:printf("U "); break;
				default:break;
				}printf("\n");
		}
	}*/
	bool is_valid_point(COORD tmp) { return !((tmp.X & 0xfff0) || (tmp.Y & 0xfff0)); }

	void create_food() {
		food.X = rand() % 16;
		food.Y = rand() % 16;
		while (board[food.X][food.Y]) { food.X = rand() % 16; food.Y = rand() % 16; }
		print(food, '*');
		del_path();
		form_path();
	}
	void set_board_true(COORD& X) { board[X.X][X.Y] = true; }
	void set_board_false(COORD& X) { board[X.X][X.Y] = false; }
	void move_to(COORD t) {
		if (t != food) {
			print(body.back(), ' ');
			set_board_false(body.back());
			body.pop_back();
			body.push_front(t); set_board_true(t);
			print(t, '*');
		}
		else {
			body.push_front(t); set_board_true(t);
			create_food();
		}del_path(); form_path();
	}
	void move() {
		COORD tmp_point = body.front();
		switch (path[body.front().X][body.front().Y]) {
		case L:tmp_point.X--; move_to(tmp_point); break;
		case R:tmp_point.X++; move_to(tmp_point); break;
		case D:tmp_point.Y++; move_to(tmp_point); break;
		case U:tmp_point.Y--; move_to(tmp_point); break;
		default:break;
		}
		Sleep(30);
	}
	void init_path() {
		for (int i = 0; i < 16; i += 2) {
			for (int j = 0; j < 16; j += 2) {
				path[i][j] = R;
				path[i + 1][j + 1] = L;
				path[i][j + 1] = U;
				path[i + 1][j] = D;
			}
		}
	}
	void set_path_board(COORD x, bool t) {
		path_board[x.X][x.Y] = t;
		path_board[x.X + 1][x.Y] = t;
		path_board[x.X][x.Y + 1] = t;
		path_board[x.X + 1][x.Y + 1] = t;
	}
	bool matrix_no_point(COORD x) {
		return board[x.X][x.Y] == false &&
			board[x.X + 1][x.Y] == false &&
			board[x.X][x.Y + 1] == false &&
			board[x.X + 1][x.Y + 1] == false;
	}
	bool path_board_not_all_true(COORD x) {
		return !(path_board[x.X][x.Y] && path_board[x.X + 1][x.Y + 1]);
	}
	void add_path_matrix(COORD x) {
		if (x.X % 2) {
			if (path_board_not_all_true(x)) {
				path[x.X][x.Y] = R;
				path[x.X + 1][x.Y + 1] = L;
				set_path_board({ x.X - 1,x.Y }, true);
				set_path_board({ x.X + 1,x.Y }, true);
			}
		}
		else {
			if (path_board_not_all_true(x)) {
				path[x.X + 1][x.Y] = D;
				path[x.X][x.Y + 1] = U;
				set_path_board({ x.X,x.Y + 1 }, true);
				set_path_board({ x.X,x.Y - 1 }, true);
			}
		}
	}
	void check_if_del(COORD x) {
		if (board[x.X][x.Y] == false && board[x.X + 1][x.Y] == false &&
			board[x.X + 1][x.Y + 1] == false && board[x.X][x.Y + 1] == false)
		{
			set_path_board(x, false);
		}
	}
	void del_path_matrix(COORD x) {
		if (x.X % 2) {
			path[x.X][x.Y] = D;
			path[x.X + 1][x.Y + 1] = U;
			check_if_del({ x.X - 1,x.Y });
			check_if_del({ x.X + 1,x.Y });
		}
		else {
			path[x.X + 1][x.Y] = L;
			path[x.X][x.Y + 1] = R;
			check_if_del({ x.X,x.Y - 1 });
			check_if_del({ x.X,x.Y + 1 });
		}
	}

	void del_path() {
		for (short i = 0; i <= 14; i += 2) {
			for (short j = 1; j < 14; j += 2) {
				if (matrix_no_point({ i,j - 1 }) || matrix_no_point({ i,j + 1 })) {
					del_path_matrix({ i, j });
				}
				if (matrix_no_point({ j - 1,i }) || matrix_no_point({ j + 1,i })) {
					del_path_matrix({ j, i });
				}
			}
		}
	}
	void form_path() {
		COORD head = body.front();
		head.X = head.X & 0xfffe;
		head.Y = head.Y & 0xfffe;
		COORD end = food;
		end.X = end.X & 0xfffe;
		end.Y = end.Y & 0xfffe;
		short dx;
		short dy;
		if (head.X > end.X)dx = -2;
		else dx = 2;
		if (head.Y > end.Y)dy = -2;
		else dy = 2;
		while (head.X != end.X) {
			short x = head.X;
			head.X += dx;
			add_path_matrix({ (x + head.X) / 2, head.Y });
		}
		//printf("\n");
	//	_print();
		while (head.Y != end.Y) {
			short y = head.Y;
			head.Y += dy;
			add_path_matrix({ end.X,(head.Y + y) / 2 });
		}
	}
};
int main()
{
	srand(time(NULL));
	snake a;
	while (true) {
		a.move();
	}
}

















//#include <iostream>
//#include <list>
//#include <iomanip>
//using namespace std;
//const int n = 5;
//
//void display(list<int> _list) {
//    if (!_list.empty()) {
//        list<int>::iterator it;
//        for (it = _list.begin(); it != _list.end(); it++)
//            cout << setw(5) << *it;
//        cout << endl;
//    }
//    else
//        cout << setw(5) << "Null list" << endl;
//}
//int main() {
//    int array[n] = { 2,7,5,3,34 };
//    list<int> list1;
//    list1.insert(list1.begin(), array, array + n);
//    display(list1);
//    list1.sort();//默认按升序排列
//   list1.reverse();
//    display(list1);
//    list<int> list2 = list1;
//    for (int i = 0; i < 4; i++)
//        list2.remove(i);
//    //将列表中小于4的元素移除，remove的作用是删除指定值的节点
//    display(list2);
//
//    list1.merge(list2);
//    display(list1);
//    display(list2);//合并后，list2变为空链表
//    list1.reverse();//逆序
//    display(list1);
//}
